

#include <util/types.h>

#include "predicates.h"
/* ========================================================================== */

/*
#define TRUE (1==1)
#define FALSE (1==0)
*/

#define abs(x) ( (x)<0 ? -(x) : (x) )
#define xor( a, b ) ( !(a) ^ !(b) )

/* ========================================================================== */
#define X 0
#define Y 1
#define Z 2
/* ========================================================================== */

// <editor-fold defaultstate="collapsed" desc="Orientation">
real _orient2d(real * pa, real * pb, real * pc) {
	/**
	 *  Use the determinant form. a, b and c are points in R².
	 * 
	 *           | a.x  a.y  1 |
	 *  det(M) = | b.x  b.y  1 | = 2 * Area(a, b, c)
	 *           | c.x  c.y  1 |
	 */
	real adx, ady;
	real bdx, bdy;
	real or;

	adx = pa[X] - pc[X];
	ady = pa[Y] - pc[Y];

	bdx = pb[X] - pc[X];
	bdy = pb[Y] - pc[Y];

	or = adx * bdy - ady * bdx;

	return or;
}
real _in_circle(real * pa, real * pb, real * pc, real * pd) {

	real adx, ady, bdx, bdy, cdx, cdy;
	real abdet, bcdet, cadet;
	real alift, blift, clift;

	real or;

	adx = pa[X] - pd[X];
	ady = pa[Y] - pd[Y];
	bdx = pb[X] - pd[X];
	bdy = pb[Y] - pd[Y];
	cdx = pc[X] - pd[X];
	cdy = pc[Y] - pd[Y];

	abdet = adx * bdy - bdx * ady;
	bcdet = bdx * cdy - cdx * bdy;
	cadet = cdx * ady - adx * cdy;
	alift = adx * adx + ady * ady;
	blift = bdx * bdx + bdy * bdy;
	clift = cdx * cdx + cdy * cdy;

	or = alift * bcdet + blift * cadet + clift * abdet;
	return or;
}
real _orient3d(real * pa, real * pb, real * pc, real * pd) {

	/**
	 *  Use the determinant form. a, b and c are points in R².
	 * 
	 *           | a.x  a.y  1 |
	 *  det(M) = | b.x  b.y  1 | = 2 * Area(a, b, c)
	 *           | c.x  c.y  1 |
	 */
	real ad[3];
	real bd[3];
	real cd[3];

	real bdxcdy, cdxbdy, cdxady, adxcdy, adxbdy, bdxady;
	real det;

	ad[X] = pa[X] - pd[X];
	bd[X] = pb[X] - pd[X];
	cd[X] = pc[X] - pd[X];

	ad[Y] = pa[Y] - pd[Y];
	bd[Y] = pb[Y] - pd[Y];
	cd[Y] = pc[Y] - pd[Y];

	ad[Z] = pa[Z] - pd[Z];
	bd[Z] = pb[Z] - pd[Z];
	cd[Z] = pc[Z] - pd[Z];

	bdxcdy = bd[X] * cd[Y];
	cdxbdy = cd[X] * bd[Y];

	cdxady = cd[X] * ad[Y];
	adxcdy = ad[X] * cd[Y];

	adxbdy = ad[X] * bd[Y];
	bdxady = bd[X] * ad[Y];

	det = ad[Z] * (bdxcdy - cdxbdy) + bd[Z] * (cdxady - adxcdy) + cd[Z] * (adxbdy - bdxady);

	return det;
}

boolean _in_rect(real * pa, real * pb, real * pc) {
	
	if (pa[X] != pb[X]) return ( pa[X] <= pc[X] && pc[X] <= pb[X]) || (pa[X] >= pc[X] && pc[X] >= pb[X]);
	else return ( pa[Y] <= pc[Y] && pc[Y] <= pb[Y]) || (pa[Y] >= pc[Y] && pc[Y] >= pb[Y]);
	
}

// </editor-fold>

/* ========================================================================== */

// <editor-fold defaultstate="collapsed" desc="Area computation">
real _area2(real * pa, real * pb, real * pc) {
	real ar;
	ar = _orient2d(pa, pb, pc);
	ar = abs(ar);
	return ar;
}
real _area(real * pa, real * pb, real * pc) {
	real ar;
	ar = _area2(pa, pb, pc);
	ar = ar / 2;
	return ar;
}
// </editor-fold>

/* ========================================================================== */

// <editor-fold defaultstate="collapsed" desc="Left verification">
boolean _in_left(real * pa, real * pb, real * pc) {
	return _orient2d(pa, pb, pc) > 0;
}
boolean _in_left_on(real * pa, real * pb, real * pc) {
	return _orient2d(pa, pb, pc) >= 0;
}
// </editor-fold>

/* ========================================================================== */

// <editor-fold defaultstate="collapsed" desc="Colinearity verification">
boolean _are_collinear(real * pa, real * pb, real * pc) {
	return _orient2d(pa, pb, pc) == 0;
}
// </editor-fold>

/* ========================================================================== */

// <editor-fold defaultstate="collapsed" desc="Right verification">
boolean _in_right(real * pa, real * pb, real * pc) {
	return _orient2d(pa, pb, pc) < 0;
}
boolean _in_right_on(real * pa, real * pb, real * pc) {
	return _orient2d(pa, pb, pc) <= 0;
}
// </editor-fold>

/* ========================================================================== */

// <editor-fold defaultstate="collapsed" desc="Intersection verification">
boolean _is_intersect_prop(real * pa, real * pb, real * pc, real * pd) {
	if (
			_are_collinear(pa, pb, pc) ||
			_are_collinear(pa, pb, pd) ||
			_are_collinear(pc, pd, pa) ||
			_are_collinear(pc, pd, pb)
			) return FALSE;

	return xor(_in_left(pa, pb, pc), _in_left(pa, pb, pd)) &&
			xor(_in_left(pc, pd, pa), _in_left(pc, pd, pb));
}
boolean _is_between(real * pa, real * pb, real * pc) {
	if (!_are_collinear(pa, pb, pc)) return FALSE;

	if (pa[X] != pb[X]) return ( pa[X] <= pc[X] && pc[X] <= pb[X]) || (pa[X] >= pc[X] && pc[X] >= pb[X]);
	else return ( pa[Y] <= pc[Y] && pc[Y] <= pb[Y]) || (pa[Y] >= pc[Y] && pc[Y] >= pb[Y]);
}
boolean is_intersect(real * pa, real * pb, real * pc, real * pd) {
	if (_is_intersect_prop(pa, pb, pc, pd)) return TRUE;
	else if (_is_between(pa, pb, pc) ||
			_is_between(pa, pb, pd) ||
			_is_between(pc, pd, pa) ||
			_is_between(pc, pd, pb)) return TRUE;
	else return FALSE;
}
// </editor-fold>

/* ========================================================================== */
/*
real _OK_in_circle(real * pa, real * pb, real * pc, real * pd) {
	
	real adx, ady, bdx, bdy, cdx, cdy;
	real abdet, bcdet, cadet;
	real alift, blift, clift;
	
	real or;

	adx = pa[X] - pd[X];
	ady = pa[Y] - pd[Y];
	bdx = pb[X] - pd[X];
	bdy = pb[Y] - pd[Y];
	cdx = pc[X] - pd[X];
	cdy = pc[Y] - pd[Y];

	abdet = adx * bdy - bdx * ady;
	bcdet = bdx * cdy - cdx * bdy;
	cadet = cdx * ady - adx * cdy;
	alift = adx * adx + ady * ady;
	blift = bdx * bdx + bdy * bdy;
	clift = cdx * cdx + cdy * cdy;

	or = alift * bcdet + blift * cadet + clift * abdet;
	return or;
}
real * _cross_product_2d(real * pa, real * cp) {
	cp[X] = pa[Y];
	cp[Y] = -pa[X];
	return cp;
}
real * _cross_product_3d(real * pa, real * pb, real * cp) {

	cp[X] = pa[Y] * pb[Z] - pa[Z] * pb[Y];
	cp[Y] = pa[X] * pb[Z] - pa[Z] * pb[X];
	cp[Z] = pa[X] * pb[Y] - pa[Y] * pb[X];

	return cp;
}
 */
